package linear;

import java.util.Stack;

public class ReverseSentence151 {
    public static String reverseWords(String s) {
        // 4 situation based on prev and cur
        // prev = " " cur = "A"
        // prev = " " cur = " "
        // prev = "A" cur = " "
        // prev =  "A" cur ="B"
        // "  hello world!  "
        Stack<String> stack = new Stack<>();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            char prev = i == 0 ? ' ' : s.charAt(i - 1);
            if (cur != ' ')
                stringBuilder.append(cur);
            if ((i == s.length() - 1 || cur == ' ') && prev != ' ') {
                stack.push(stringBuilder.toString());
                stringBuilder = new StringBuilder();
            }
        }
//        System.out.println("Here");
        while (!stack.isEmpty())
            if (stack.size() != 1)
                stringBuilder.append(stack.pop() + " ");
            else
                stringBuilder.append(stack.pop());
        return stringBuilder.toString();
    }
    public static String reverseWords2(String s) {
        // 4 situation based on prev and cur
        // prev = " " cur = "A"
        // prev = " " cur = " "
        // prev = "A" cur = " "
        // prev =  "A" cur ="B"
        // "  hello world!  "
        StringBuilder stringBuilder = new StringBuilder();
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            char prev = i == 0 ? ' ' : s.charAt(i - 1);
            if (cur != ' ')
                stringBuilder.append(cur);
            if ((cur == ' '&& prev != ' ')){
                res = new StringBuilder(" ").append(stringBuilder).append(res);
                stringBuilder = new StringBuilder();}
            else if(i == s.length() -1 && prev != ' ')
                res = stringBuilder.append(res);
        }
        return res.toString().trim();
    }

    public static void main(String[] args) {
        String res = reverseWords("  hello world!  ");
        System.out.println(res);
    }
}
